package 力扣热题100;

public class LeetCode34 {
    public boolean exist(char[][] board, String word) {
        int k=0;
        char[][]board1=new char[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(judge(board1,word,k,i,j)==true){
                   return true;
               }
            }
        }
        return false;
    }

    private boolean judge(char[][] board, String word, int k, int i, int j) {
        if(k==word.length()){
            return true;
        }
        if(i>= board.length||j>= board[0].length||i<0||j<0){
            return false;
        }
        if(board[i][j]!=word.charAt(k)){
            return false;
        }else {
            board[i][j]=0;
        }
        if( judge(board,word,k+1,i,j+1)||judge(board,word,k+1,i+1,j)
                    ||judge(board,word,k+1,i-1,j)||judge(board,word,k+1,i,j-1)){
            return true;
        }
        board[i][j]=word.charAt(k);
        return false;
    }

    public static void main(String[] args) {
        LeetCode34 leetCode34=new LeetCode34();
        char[][]arr=new char[][]{{'A','B','C','E'},{'S','F','E','S'},{'A','D','E','E'}};
        leetCode34.exist(arr,new String("ABCEFSADEESE"));
    }
}
